package com.dong.algorithm.novice.linkedlist;

/**
 * 经典题目：单双链表的反转
 * 给定一个单链表的头Head，完成链表的逆序调整
 * 给定一个双链表的头Head，完成链表的逆序调整
 *
 * @author by jiweidong on 2021/11/29.
 */
public class Arg01_ReverseList {

    private static class Node {
        private int value;
        private Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node reverseLinkedList(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    private static class DoubleNode {
        private int value;
        private DoubleNode last;
        private DoubleNode next;

        public DoubleNode(int data) {
            this.value = data;
        }
    }

    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }
}
